package com.leetcode.solution.s9x;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses93 {
    public static void main(String[] args) {
//        List<String> lst = new RestoreIpAddresses93().restoreIpAddresses("25525511135");
        List<String> lst = new RestoreIpAddresses93().restoreIpAddresses("0000");
        if (lst == null) {
            System.out.println("error");
            return;
        }
        for (String s : lst) {
            System.out.println(s);
        }
    }

    public static final int IP_SIZE = 4;
    private List<String> result;
    private int[] ipAddrs;
    public List<String> restoreIpAddresses(String s) {
        result = new ArrayList<>();
        ipAddrs = new int[IP_SIZE];
        dfs(s, 0, 0);

        return result;
    }

    private void dfs(String s, int startIdx, int len) {
        // 如果找到4位IP地址，则解析拼接地址串
        if (len == IP_SIZE) {
            if (s.length() == startIdx) {
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < IP_SIZE; i++) {
                    sb.append(".").append(ipAddrs[i]);
                }

                result.add(sb.substring(1));
            }

            return;
        }

        if (startIdx == s.length()) {
            return;
        }

        if (s.charAt(startIdx) == '0') {
            ipAddrs[len] = 0;
            dfs(s, startIdx + 1, len + 1);
            return;
        }

        int currAddr = 0;
        for (int currEndIdx = startIdx; currEndIdx < s.length(); currEndIdx++) {
            currAddr  = currAddr * 10 + (s.charAt(currEndIdx) - '0');
            if (0 <= currAddr && currAddr <= 255) {
                ipAddrs[len] = currAddr;
                dfs(s, currEndIdx + 1, len + 1);
            } else {
                return;
            }
        }
    }
}
